﻿package tree;

import queue.SeqQueue;
import stack.SeqStack;

public class BinaryTree<T> implements IBinaryTree<T> {
    public BinaryNode<T> root;                  //根结点，二叉链表结点结构

    public BinaryTree() {
        this.root = null;
    }

    public static void main(String[] args) {

        //                   A
        //                /     \
        //               B       C
        //             /   \    /  \
        //            D     E   F   G
        //                 /     \
        //                H       I
        //                       /
        //                      J

        // 初始化树
        BinaryTree<Character> btree = new BinaryTree<Character>();
        BinaryNode<Character> nodeA = btree.insert('A');

        // 左子树
        BinaryNode<Character> nodeB = btree.insert(nodeA, 'B', true);

        // 右子树
        BinaryNode<Character> nodeC = btree.insert(nodeA, 'C', false);


        System.out.println(btree);
        System.out.println(btree.size());
        System.out.println(btree.height());

        // 遍历
        System.out.println("preOrder, inOrder, postOrder:");
        btree.preOrder();
        btree.inOrder();
        btree.postOrder();

        System.out.println("preOrderTraverse, inOrderTraverse, levelOrder:");
        btree.preOrderTraverse();
        btree.inOrderTraverse();
        btree.levelOrder();

    }

    @Override
    public boolean isEmpty() {
        return this.root==null;
    }

    //插入x作为根结点，原根结点作为x的左孩子；返回插入结点
    @Override
    public BinaryNode<T> insert(T x) {
        if(x!=null)
        	this.root=new BinaryNode<T>(x,this.root,null);
    }

    //插入x为parent结点的左/右孩子，leftChild指定孩子，取值为true（左）、false（右）；
    //parent的原左/右孩子成为x结点的左/右孩子；返回插入结点。
    @Override
    public BinaryNode<T> insert(BinaryNode<T> parent, T x, boolean leftChild) {
       if(x==null||p==null)
    	   return null;
       if(left)  //插入x为p的结点的左/右孩子，返回插入结点
    	   return p.left=new BinaryNode<T>(x,p.left,null);
       return p.right=new BinaryNode<T>(x,null,p.right);
    }

    @Override
    public String toString() {
        return toString(this.root);
    }

    private String toString(BinaryNode<T> p) {
        
    }

    @Override
    public int size() {
        return size(root);
    }

    private int size(BinaryNode<T> p) {
        return 0;
    }

    @Override
    public int height() {
        return height(root);
    }

    private int height(BinaryNode<T> p) {
        return 0;
    }

    @Override
    public void remove(BinaryNode<T> parent, boolean leftChild) {
    		if(p!=null) {
    			if(left)
    				p.left=null;
    			else
    				p.right=null;
    		}
    }

    @Override
    public void clear() {
    	this.root=null;
    }


    @Override
    public void preOrder() {
        preOrder(this.root);
        System.out.println();
    }

    private void preOrder(BinaryNode<T> p) {
    		if(p!=null) {
    			System.out.print(p.data+" ");
    			for(TreeNode<T> q=p.child;q!=null;q=q.sibling)
    				preorder2(q);
    		}
    }

    @Override
    public void inOrder() {
        inOrder(this.root);
        System.out.println();
    }
    private void inOrder(BinaryNode<T> p) {  //中根次序遍历以p结点为根的子树，递归方法
    	if(p!=null) {
    		inorder(p.left);
    		System.out.print(p.data.toString()+" ");
    		inorder(p.right);
    	}
    }

    @Override
    public void postOrder() {
        postOrder(this.root);
        System.out.println();
    }
    private void postOrder(BinaryNode<T> p) {
    	if(p!=null) {
    		postorder(p.left);
    		postorder(p.right);
    		System.out.print(p.data.toString()+" ");
    	}
    }

    @Override
    public void preOrderTraverse() {

    }

    @Override
    public void inOrderTraverse() {

    }

    @Override
    public void levelOrder() {

    }

}
